package com.wyw.leetcode.learning.simple;


/**
 * leetcode topic 121
 *  买卖股票的最佳时机
 *      给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
 *      你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
 *      返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0
 *
 * @Author Mr Wu    yewen.wu.china@gmail.com
 * <p>
 * Update History:
 * Author        Time            Content
 */
public class Topic121 {

    public static void main(String[] args) {
//        int[] prices = new int[]{7,1,5,3,6,4};
        int[] prices = new int[]{7,6,5,4,3,2,1};
        System.out.println(maxProfit(prices));
    }

    public static int maxProfit(int[] prices) {
        int min = prices[0];
        int result = 0;
        int size = prices.length;
        for(int i =1; i< size; i++) {
            if(prices[i] < min) {
                min = prices[i];
            } else if (prices[i] - min > result) {
                result = prices[i] - min;
            }
        }
        return result;
    }

    /**
     * 暴力
     */
    public static int maxProfitq(int[] prices) {
        int result = 0;
        int size = prices.length;
        for (int i = 0; i < size - 1; i++) {
            for (int j = i + 1; j < size; j++) {
                int profit = prices[j] - prices[i];
                if (profit > result) {
                    result = profit;
                }
            }
        }
        return result;
    }

    /**
     * 减少变量次数
     */
    public static int maxProfitq1(int[] prices) {
        int min = Integer.MAX_VALUE;
        int max = 0;
        for (int price : prices) {
            if (min > price) {
                min = price;
            } else if (price - min > max) {
                max = price - min;
            }
        }
        return max;

    }

}
